package com.kingwood.algorithm.test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author 22025812
 * @Description: 回溯算法，和动态规划很像，但是回溯算法是动态规划的特例
 * @Date: 2024/3/4 16:25
 * @Modified By：
 * @Version 1.0
 */
public class HuiSu {

    static class Card {
        int num;
        char color;
        public Card(int num, String color) {
            this.num = num;
            this.color = color.charAt(0);
        }
    }

    /**
     * 连续出牌数量
     * https://fcqian.blog.csdn.net/article/details/127711078
     * @param nums
     * @param colors
     * @return
     */
    public static int maxLongOfLianXuShouPai(int[] nums, String[] colors) {
        int max = 0;
        int len = nums.length;
        Card[] cards = new Card[len];
        for (int i = 0; i < len; i++) {
            cards[i] = new Card(nums[i], colors[i]);
        }

        int[] ans = {0};
        boolean[] used = new boolean[len];
        backtrack(cards, used, null, 0, ans);
        return ans[0];
    }

    public static void backtrack(Card[] cards, boolean[] used, Card last, int count, int[] ans) {
        ans[0] = Math.max(ans[0], count);
        for (int i = 0; i < cards.length; i++) {
            if (used[i]) {
                continue;
            }

            Card cur = cards[i];
            if (last != null && last.num != cur.num && last.color != cur.color) {
                continue;
            }

            used[i] = true;
            backtrack(cards, used, cards[i], count + 1, ans);
            used[i] = false;
        }
    }

    public static void backtrack1(Card[] cards, boolean[] used, Card last, int count, int[] ans) {
        ans[0] = Math.max(count, ans[0]);

        for (int i=0; i<cards.length; i++) {
            if (used[i]) {
                continue;
            }

            Card cur = cards[i];
            if (last != null && last.num != cur.num && last.color != cur.color) {
                continue;
            }

            used[i] = true;
            backtrack1(cards, used, cur, count+1, ans);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        String[] colors = scanner.nextLine().split(" ");
        System.out.println(maxLongOfLianXuShouPai(nums, colors));
    }
}
